1. Field of Invention
The present invention relates to the field of computer graphics and in particular concerns a method and apparatus for determining how a computer-generated polygon shape should be filled.
2. Background Discussion
Most modern computer graphic systems use raster technology to display images. In raster technology displays, lines, characters and solid areas, usually represented as polygons, are stored in computer memory as groups of fundamental units known as picture elements or "pixels." Pixels are arranged into horizontal strings called raster lines. These raster lines are organized vertically to form a pixel matrix or "raster". Images are formed on the raster and are scanned out sequentially one raster line at a time onto the display screen by an electron beam which varies the intensity of each pixel.
A polygon is comprised of a number of sides or edges which are represented in computer memory as pairs of Cartesian coordinates (x,y) corresponding to the edge vertices. Traditionally, once the edges defining the polygon were stored in memory, an algorithm known as the "standard-fill" or "scan-line" algorithm, horizontally scans each raster line computinq the number of polygon edges intersected by the scan-line. When the scan-line intersects a polygon edge it determines the number of polygon edges currently crossed. If the number crossed edges is odd, for example, three, indicating that the current crossed edge is the third thus far, the string of pixels in that particular raster line is modified or "filled" from the current edge intersect till the next edge intersect, at which point the crossed edge count becomes even. When the crossed edge count becomes even, the pixels along the raster line from the current crossed edge intersect to the next edge intersect are not filled.
The scan-line algorithm works adequately with simple polygon shapes, however, it yields undesirable results in special cases of horizontal edges or intersecting vertices at a point of intersection along the currently scanned raster line.
Accordingly, it is an object of the present invention to provide an improved scan-line algorithm which is capable of determining when to perform a fill between polygon edges, particularly in the special cases of intersecting vertices or horizontal edges along the scan-line.
It is a further object of the present invention to provide an apparatus for executing the above mentioned method in a computer graphic system.